package MDVRPTW;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class MDVRPTW {

	//优化目标个数
	public static final int NUMOBJECTS=4;
	
	//总顾客数
	private int csmNum;
	//总车场数
	private int deportNum;
	
	//每个车场拥有车辆数
	private int nCars;
	//车辆载重上限
	private double limitLoad;
	//车辆容量上限
	private double limitCapacity;
	//车辆可服务的最长时间
	private double limitTime;
	//车辆速度
	private double velocity=1;
	
	//顾客情况集合
	LinkedList<Customer> customers = new LinkedList<Customer>();
	//车场情况集合
	LinkedList<Deport> deports = new LinkedList<Deport>();
	
	//初始化
	public MDVRPTW(String filePath){
		
		try {
			Load load=new Load(filePath);
			this.deports=load.getDeports();
			this.customers=load.getCustomers();
			this.limitCapacity=load.getLimitCapacity();
			this.limitLoad=load.getLimitLoad();
			this.limitTime=load.getLimitTime();
			this.nCars=load.getCarNum();
			this.csmNum=load.getCsmNum();
			this.deportNum=load.getDeportNum();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	/**
	 * 获取两点距离的方法
	 * 
	 * @param p1
	 * @param p2
	 * @return 任意两点间的欧氏距离
	 */
	public double getDistance(Point p1, Point p2) {
		double xy1[] = p1.getPoint();
		double xy2[] = p2.getPoint();

		double X1 = xy1[0];
		double Y1 = xy1[1];
		double X2 = xy2[0];
		double Y2 = xy2[1];

		return Math.sqrt(Math.pow(X1 - X2, 2) + Math.pow(Y1 - Y2, 2));
	}
	
	/**
	 * 计算损失值算法（暂时没写）
	 * 
	 * @param cars 需要的车辆数
	 * @param distance 方案总路径长度
	 * @param voilation 违背时间窗约束时间程度
	 * @param variance 各辆车的工作时间方差
	 * @return 损失值
	 */
	private double getLossValue(int cars,double distance,double voilation,double variance){
		return 0;
	}
	
	/**
	 * 初始染色体的生成
	 */
	public Solution init(){
		
		//存储车辆路径集合
		LinkedList<Car> cars = new LinkedList<Car>();
		//创建新集合，存储已获取的顾客，并进行随机排列
		LinkedList<Customer> tempCustomers=new LinkedList<Customer>();
		tempCustomers=(LinkedList<Customer>) customers.clone();
		Collections.shuffle(tempCustomers);
		
		//声明一个数组记录车场车辆使用情况
		int[] deportCount=new int[deportNum];
		for (int i=0;i<deportNum;i++) {
			deportCount[i]=nCars;
		}
		
		//
		while(tempCustomers.size()>0){
			
			//声明一条临时染色体，记录当前最小损失值的染色体
			Car bestCar=null;
			double tbestDistance=Double.MAX_VALUE;//保存路径最佳位置插入的路径长度
			double tbestVoilation=Double.MAX_VALUE;//保存路径最佳位置插入的时间违背度
			//取出一个顾客
			Customer csm=tempCustomers.getFirst();
			tempCustomers.removeFirst();
			//默认用尽量少的车辆为优，先尝试将顾客放入已有的染色体中
			for(int i=0;i<cars.size();i++){
				Car nowCar=cars.get(i);
				//先检测是否会超重或超出容量
				if((csm.getWeight()+nowCar.getLoad()<limitLoad)&&(csm.getVolume()+nowCar.getCapacity()<limitCapacity)){
					
					for(int j=0;j<nowCar.getRoute().size()-1;j++){
						double tDistance;//保存尝试插入顾客后该染色体的路径长度
						double tempVoilation = 0;//保存临时的惩罚系数，惩罚系数指违背时间窗约定的情况，各顾客延期时间的和
						tDistance=nowCar.getDistance()-getDistance(nowCar.getRoute().get(j), nowCar.getRoute().get(j+1))+getDistance(nowCar.getRoute().get(j), csm)+getDistance(csm, nowCar.getRoute().get(j+1));
						//申请一个临时空间保存尝试插入的点后的染色体
						Car tempCar=new Car();
						tempCar.setNum(nowCar.getNum());
						tempCar.setDno(nowCar.getDno());
						tempCar.setRoute((LinkedList<Customer>)nowCar.getRoute().clone());//拷贝原路径
						tempCar.getRoute().add(j+1, csm);//将取出的顾客插入路径
						tempCar.getEndTime().add(0.0);
						for(int k=1;k<tempCar.getRoute().size();k++){
							//记录到该节点的时间
							double tST=tempCar.getEndTime().get(k-1)+getDistance(tempCar.getRoute().get(k-1), tempCar.getRoute().get(k))/velocity;
							//求该点的等待时间
							double tWait=tST>=tempCar.getRoute().get(k).getEST()?0:tempCar.getRoute().get(k).getEST()-tST;
							//累计违背时间系数
							tempVoilation+=tST>tempCar.getRoute().get(k).getLST()?tST-tempCar.getRoute().get(k).getLST():0;
							if(tempVoilation>tbestVoilation)
								break;//如果违背时间系数已经大于已知最佳插入位置，则放弃此插入计划
							tempCar.getEndTime().add(tST+tWait+tempCar.getRoute().get(k).getServiceTime());
						}
						if(tempVoilation>tbestVoilation)
							continue;//如果违背时间系数已经大于已知最佳插入位置，则放弃此插入计划
						else if(tDistance>tbestDistance)
							continue;
						else{
							tempCar.setDistance(tDistance);
							tempCar.setCapacity(nowCar.getCapacity()+csm.getVolume());
							tempCar.setVoilation(tempVoilation);
							tempCar.setLoad(nowCar.getLoad()+csm.getWeight());
							bestCar=tempCar;
							tbestDistance=tDistance;
							tbestVoilation=tempVoilation;
						}
					}
					
				}
			}
			if(bestCar==null||tbestVoilation>0){//该情况下说明原本没有染色体或者原本染色体将违背硬时间窗窗约定，尝试新建染色体
				for(int i=0;i<deportNum;i++){
					if(deportCount[i]>0){
						Car newCar=new Car();
						newCar.setDno(i);
						newCar.setNum(nCars-deportCount[i]);
						
						//将车场也记为节点
						Customer sDeport=new Customer();
						sDeport.setNum(i+1+csmNum);
						sDeport.setEST(0);
						sDeport.setLST(limitTime);
						sDeport.setServiceTime(0.0);
						sDeport.setX(deports.get(i).getX());
						sDeport.setY(deports.get(i).getY());
						Customer eDeport=new Customer();
						eDeport.setNum(i+1+csmNum);
						eDeport.setEST(0);
						eDeport.setLST(limitTime);
						eDeport.setServiceTime(0.0);
						eDeport.setX(deports.get(i).getX());
						eDeport.setY(deports.get(i).getY());
						
						//将车场节点插入路径中
						newCar.getRoute().add(sDeport);
						newCar.getRoute().add(csm);
						newCar.setLoad(csm.getWeight());
						newCar.setCapacity(csm.getVolume());
						newCar.setDistance(getDistance(sDeport, csm)+getDistance(csm, eDeport));
						//计算结束时间和时间窗违背系数
						newCar.getEndTime().add(0.0);
						double tsTime=getDistance(sDeport, csm)/velocity;
						double tWait=tsTime>=csm.getEST()?0:csm.getEST()-tsTime;
						newCar.getEndTime().add(tsTime+tWait+csm.getServiceTime());
						double tVoilation=tsTime>=csm.getLST()?tsTime-csm.getLST():0;
						newCar.getRoute().add(eDeport);
						tsTime=newCar.getEndTime().getLast()+getDistance(csm, eDeport)/velocity;
						newCar.getEndTime().add(tsTime);
						tVoilation+=tsTime>=limitTime?0:limitTime-tsTime;
						newCar.setVoilation(tVoilation);
						if(tVoilation>tbestVoilation)
							continue;//如果违背时间系数已经大于已知最佳插入位置，则放弃此插入计划
						else if(newCar.getDistance()>tbestDistance)
							continue;
						else{
							bestCar=newCar;
							tbestDistance=bestCar.getDistance();
							tbestVoilation=tVoilation;
						}
					}
				}
			}
			//替换或者将染色体加入染色体组
			if(bestCar!=null){
				int existSign=0;
				for(int i=0;i<cars.size();i++){
					if(cars.get(i).getDno()==bestCar.getDno()&&cars.get(i).getNum()==bestCar.getNum()){
						existSign=1;
						cars.remove(i);
						cars.add(i, bestCar);
					}
				}
				if(existSign==0){
					cars.add(bestCar);
					deportCount[bestCar.getDno()]--;
				}
			}
			//bestCar.print();
		}
		Solution solution=new Solution();
		//将数据存入solution中
		solution.setCars(cars);
		solution.setTotalCars();
		solution.setTotalDistance();
		solution.setTotalVoilation();
		solution.setTimeVariance();
		solution.setDeportCount(deportCount);
		//solution.print();
		if(solution.getTotalVoilation()==0)
			solution.print();
		return solution;
	}
	
	public Solution exchange(Solution solution){
		//将方案重新拷贝一份,防止两个方案相互干扰
		Solution newSolution=new Solution(solution);
		LinkedList<Car> carList=newSolution.getCars();
		int[] deportCount=newSolution.getDeportCount();
		//获得第一个随机数，用于选择一条移除一个节点的染色体
		int index1=(int) (Math.random()*carList.size());
		
		//保存移除的染色体
		Car aCar=carList.remove(index1);
		//获得第二个随机数，用于选择染色体中一个点进行移除
		int index2=(int) (Math.random()*(aCar.getRoute().size()-2));
		//保存移除的点
		Customer csm=aCar.getRoute().remove(index2+1);
		//计算移除点后的染色体情况
		if(aCar.getRoute().size()>2){		
			aCar.setLoad(aCar.getLoad()-csm.getWeight());
			aCar.setCapacity(aCar.getCapacity()-csm.getVolume());
			double tDistance=0;
			double tVoilation=0;
			aCar.getEndTime().removeLast();
			for(int i=0;i<aCar.getRoute().size()-1;i++){
				tDistance+=getDistance(aCar.getRoute().get(i), aCar.getRoute().get(i+1));
				double tST=aCar.getEndTime().get(i)+getDistance(aCar.getRoute().get(i), aCar.getRoute().get(i+1))/velocity;
				double tWait=tST>=aCar.getRoute().get(i+1).getEST()?0:aCar.getRoute().get(i+1).getEST()-tST;
				tVoilation+=tST>=aCar.getRoute().get(i+1).getLST()?tST-aCar.getRoute().get(i+1).getLST():0;
				aCar.getEndTime().set(i+1, tST+tWait+aCar.getRoute().get(i+1).getServiceTime());
			}
			aCar.setDistance(tDistance);
			aCar.setVoilation(tVoilation);
		}
		else{
			for (Car car : carList) {
				if(car.getDno()==aCar.getDno()&&car.getNum()>aCar.getNum()){
					car.setNum(car.getNum()-1);
				}
			}
			deportCount[aCar.getDno()]++;
		}
		//判断取出的节点是否能插入其他路径中，如果不能，则返回原来的方案，放弃本次领域搜索
		boolean isInsertable=false;
		for(int i=0;i<carList.size();i++){//判断其他路径是否能满足负重和体积
			if((csm.getWeight()+carList.get(i).getLoad()<limitLoad)&&(csm.getVolume()+carList.get(i).getCapacity()<limitCapacity)){
				isInsertable=true;
				break;
			}
		}
		for(int i=0;i<deportCount.length;i++){
			if(deportCount[i]>0){
				isInsertable=true;
				break;
			}
		}
		if(!isInsertable){
			return solution;
		}
		//***********************************************************************************************
		boolean sign=false;//声明一个标志，当随机取得的染色体能插入变异点时，令sign=1,结束循环
		while(!sign){
			//获得第三个随机数，用于选择插入的染色体
			int index3=(int) (Math.random()*(carList.size()+deportCount.length));
			if(index3>=carList.size()){//前面0-carList.size()-1指已存在的染色体，后面的数字则代表从index-carList.size()个车场重新生成染色体并插入该点
				if(deportCount[index3-carList.size()]>0){
					int t_index=index3-carList.size();
					Car newCar=new Car();
					newCar.setDno(t_index);
					newCar.setNum(nCars-deportCount[t_index]);
					
					//将车场也记为节点
					Customer sDeport=new Customer();
					sDeport.setNum(t_index+csmNum+1);
					sDeport.setEST(0);
					sDeport.setLST(limitTime);
					sDeport.setServiceTime(0.0);
					sDeport.setX(deports.get(t_index).getX());
					sDeport.setY(deports.get(t_index).getY());
					Customer eDeport=new Customer();
					eDeport.setNum(t_index+csmNum+1);
					eDeport.setEST(0);
					eDeport.setLST(limitTime);
					eDeport.setServiceTime(0.0);
					eDeport.setX(deports.get(t_index).getX());
					eDeport.setY(deports.get(t_index).getY());
					
					//将车场节点插入路径中
					newCar.getRoute().add(sDeport);
					newCar.getRoute().add(csm);
					newCar.setLoad(csm.getWeight());
					newCar.setCapacity(csm.getVolume());
					newCar.setDistance(getDistance(sDeport, csm)+getDistance(csm, eDeport));
					//计算结束时间和时间窗违背系数
					newCar.getEndTime().add(0.0);
					double tsTime=getDistance(sDeport, csm)/velocity;
					double tWait=tsTime>=csm.getEST()?0:csm.getEST()-tsTime;
					newCar.getEndTime().add(tsTime+tWait+csm.getServiceTime());
					double tVoilation=tsTime>=csm.getLST()?tsTime-csm.getLST():0;
					newCar.getRoute().add(eDeport);
					tsTime=newCar.getEndTime().getLast()+getDistance(csm, eDeport)/velocity;
					newCar.getEndTime().add(tsTime);
					tVoilation+=tsTime>=limitTime?0:limitTime-tsTime;
					newCar.setVoilation(tVoilation);
					carList.add(newCar);
					if(aCar.getRoute().size()>2){
						carList.add(aCar);
					}
					sign=true;
					deportCount[t_index]--;
				}
			}
			else{//如果小于染色体数量，说明将从已有染色体中选一个插入，此时插入只比较距离，而不考虑时间违背程度
				//声明一条临时染色体，记录当前最小损失值的染色体
				Car bestCar=null;
				double tbestDistance=Double.MAX_VALUE;//保存路径最佳位置插入的路径长度
				double tbestVoilation=Double.MAX_VALUE;//保存路径最佳位置插入的时间违背度
				int i=index3;
				Car nowCar=carList.get(i);
				//先检测是否会超重或超出容量
				if((csm.getWeight()+nowCar.getLoad()<limitLoad)&&(csm.getVolume()+nowCar.getCapacity()<limitCapacity)){
					carList.remove(i);
					for(int j=0;j<nowCar.getRoute().size()-1;j++){
						double tDistance;//保存尝试插入顾客后该染色体的路径长度
						double tempVoilation = 0;//保存临时的惩罚系数，惩罚系数指违背时间窗约定的情况，各顾客延期时间的和
						tDistance=nowCar.getDistance()-getDistance(nowCar.getRoute().get(j), nowCar.getRoute().get(j+1))+getDistance(nowCar.getRoute().get(j), csm)+getDistance(csm, nowCar.getRoute().get(j+1));
						//申请一个临时空间保存尝试插入的点后的染色体
						Car tempCar=new Car();
						tempCar.setNum(nowCar.getNum());
						tempCar.setDno(nowCar.getDno());
						tempCar.setRoute((LinkedList<Customer>)nowCar.getRoute().clone());//拷贝原路径
						tempCar.getRoute().add(j+1, csm);//将取出的顾客插入路径
						tempCar.getEndTime().add(0.0);
						for(int k=1;k<tempCar.getRoute().size();k++){
							//记录到该节点的时间
							double tST=tempCar.getEndTime().get(k-1)+getDistance(tempCar.getRoute().get(k-1), tempCar.getRoute().get(k))/velocity;
							//求该点的等待时间
							double tWait=tST>=tempCar.getRoute().get(k).getEST()?0:tempCar.getRoute().get(k).getEST()-tST;
							//累计违背时间系数
							tempVoilation+=tST>tempCar.getRoute().get(k).getLST()?tST-tempCar.getRoute().get(k).getLST():0;
							tempCar.getEndTime().add(tST+tWait+tempCar.getRoute().get(k).getServiceTime());
						}
						if(tDistance>tbestDistance)
							continue;
						else{
							tempCar.setDistance(tDistance);
							tempCar.setCapacity(nowCar.getCapacity()+csm.getVolume());
							tempCar.setVoilation(tempVoilation);
							tempCar.setLoad(nowCar.getLoad()+csm.getWeight());
							bestCar=tempCar;
							tbestDistance=tDistance;
							tbestVoilation=tempVoilation;
						}
					}
					carList.add(bestCar);
					if(aCar.getRoute().size()>2){
						carList.add(aCar);
					}
					sign=true;
				}
			}
		}
		//重新计算solution
		newSolution.setCars(carList);
		newSolution.setDeportCount(deportCount);
		newSolution.setTotalCars();
		newSolution.setTotalDistance();
		newSolution.setTotalVoilation();
		newSolution.setTimeVariance();
		newSolution.setDeportCount(deportCount);
		//solution.print();
		//System.out.println("选择了"+aCar.getDno()+"-"+aCar.getNum()+"上的"+csm.getNum()+"插入到");
		//newSolution.print();
//		if(newSolution.getTotalVoilation()==0)
//			newSolution.print();
		return newSolution;
	}
	
	//领域搜索算法
	public Solution neighbor(Solution solution){
		
		Solution temp=new Solution(solution);
		temp=exchange(temp);
		return temp;
	}
	
}
